\chapter{Calcul de l'aire}

	Nous nous intéressons au problème simple du calcul de l'aire :
	\[
		A(r) = \pi * r^2
	\]

\section{Calcul en opérations flottantes}
	
	En calcul à précision flottante, on obtient, avec un rayon de 534 mètres :
	\[
		A_0(534) = 895 843,99\ldots
	\]	
	
\section{Calcul en entiers}
	
	%Q1
\subsection{Question 1 - Calcul en entiers}

	\begin{align*}
		A_1(r) &= \frac{314 * r * r}{100} \\
		A_1(534) &= 895 389,84\ldots \\
		\Delta_1 &= A_0 - A_1 \approx 454
	\end{align*}

	%Q2
\subsection{Question 2 - Calcul en entiers, version plus précise}

	\begin{align*}
		A_2(r) &= \frac{31415 * r * r}{1000} \\
		A_2(534) &= 895 817,57\ldots \\
		\Delta_2 &= A_0 - A_2 \approx 26
	\end{align*}
	
	%Q3
\subsection{Question 3 - Application en assembleur}
	L'utilisation du calcul en entiers avec pi représenté par $\frac{31415}{1000}$ génère rapidement des résultats erronés, pour cause de dépassement de capacité. Par exemple, pour un rayon de 534 mètres, le produit $534 \cdot 534 \cdot 31415$ dépasse $2^{31} -2$. \\
	Pour le code, cf. fichier aire\_v1.s.
	
	Une solution pour retarder le dépassement de capacité consiste à inverser les opérations, en divisant par 10 000 avant de faire la deuxième la multiplication. Cette fois-ci le calcul de l'aire d'un cercle de rayon 534 ne génère pas de dépassement, mais au prix d'une perte de précision importante.
	En effet, la division entière par 10 000 fait perdre beaucoup d'information, et l'erreur générée est ensuite multipliée par le rayon. \\
	Pour le second code, cf. fichier aire\_v2.s.

\section{Fractions continues}

	%Q4
\subsection{Question 4 - Vérifier que $a_1 = q_1 = \lfloor x\rfloor$ et $ b_1 = 1 $.}	
	
	$a_1$ et $b_1$ sont les valeurs obtenues par un développement en fraction continue de rang 1, ainsi : 
	\[ 
		\frac{a_1}{b_1}  \simeq q_1 + e1,
	\]	
	$q_1$ étant la partie entière de $x$ et $e1$ la partie décimale.
	
	Dans la forme réduite, le terme d'erreur est négligé, ainsi :
	\[ 
		\frac{a_1}{b_1} = q_1
	\]
	Il est donc clair que $a_1 = q_1 = \lfloor x\rfloor$ et $b_1$ ne peut valoir que 1.
	
	
	%Q5
\subsection{Question 5 - Démonstration}
	
	Montrer par récurrence que :
	\[
		\left\{
			\begin{array}{rcr}
				a_n &= q_n \cdot a_{n-1} + a_{n-2} \\
				b_n &= q_n \cdot b_{n-1} + a_{n-2} \\
			\end{array}
		\right.
	\]
	
	Ecrivons les fractions continues d'ordre $n$ et $n-1$ : 
	$$
		\frac{a_{n-1}}{b_{n-1}} = 
		q_1 + \frac
		{1}
		{q_2 + \frac
			{1}
			{\ldots + \frac
				{1}
				{q_{n-1}}
			}
		}
	$$

	$$
		\frac{a_{n}}{b_{n}} = 
		q_1 + \frac
		{1}
		{q_2 + \frac
			{1}
			{\ldots + \frac
				{1}
				{q_{n-1} + \frac
					{1}
					{q_n}
				}
			}
		}
	$$
	
	On remarque que pour passer de l'une à l'autre il suffit de poser : 
	\[
		q'_{n-1} =  q_{n-1} + \frac{1}{q_n} 
	\].
	
	Réutilisons cela dans l'hypothèse de récurrence  : 
	
	$$
		\frac
			{a_{n-1}}
			{b_{n-1}} 
		=
		\frac
			{q_{n-1} \cdot a_{n-2} + a_{n-3}}
			{q_{n-1} \cdot b_{n-2} + b_{n-3}}
	$$

	On obtient :
	$$
		\frac
			{a_{n}}
			{b_{n}} 
		=
		\frac
			{q'_{n-1} \cdot a_{n-2} + a_{n-3}}
			{q'_{n-1} \cdot b_{n-2} + b_{n-3}}
	$$

	Remplaçons $q'_{n-1}$ par $q_{n-1} + \frac{1}{q_n}$, et développons :
	
	\begin{align*}
		\frac
			{a_{n}}
			{b_{n}} 
		&=
		\frac
			{(q_{n-1} + \frac{1}{q_n}) \cdot a_{n-2} + a_{n-3}}
			{(q_{n-1} + \frac{1}{q_n}) \cdot b_{n-2} + b_{n-3}} \\
		&=
		\frac
			{(q_{n-1} \cdot a_{n-2}) + (\frac{1}{q_n} \cdot a_{n-2}) + a_{n-3}}
			{(q_{n-1} \cdot b_{n-2}) + (\frac{1}{q_n} \cdot b_{n-2}) + b_{n-3}}
	\end{align*}
	
	or, d'après l'hypothèse de récurrence :
	\begin{align*}
		a_{n-1} &= q_{n-1} \cdot a_{n-2} + a_{n-3} \\
		b_{n-1} &= q_{n-1} \cdot b_{n-2} + b_{n-3} \\
		ainsi : a_{n-3} &= a_{n-1} - q_{n-1} \cdot a_{n-2} \\
		et : b_{n-3} &= b_{n-1} - q_{n-1} \cdot b_{n-2} \\
	\end{align*}
		
	Réinjectons-les :
	\begin{align*}
		\frac
			{a_{n}}
			{b_{n}} 
		&=
		\frac
			{(q_{n-1} \cdot a_{n-2}) + (\frac{1}{q_n} \cdot a_{n-2}) + a_{n-1} - (q_{n-1} \cdot a_{n-2})}
			{(q_{n-1} \cdot b_{n-2}) + (\frac{1}{q_n} \cdot b_{n-2}) +  b_{n-1} - (q_{n-1} \cdot b_{n-2})}\\
		&=
		\frac
			{ a_{n-1} + (\frac{1}{q_n} \cdot a_{n-2}) }
			{ b_{n-1} + (\frac{1}{q_n} \cdot b_{n-2}) }
	\end{align*}
	
	Enfin, en multipliant par $\frac{q_n}{q_n}$
	\begin{align*}
		on obtient : \frac
			{a_{n}}
			{b_{n}} 
		&=
		\frac
			{ {q_n} \cdot a_{n-1} + a_{n-2} }
			{ {q_n} \cdot b_{n-1} + b_{n-2} }
	\end{align*}
	
	%Q6
\subsection{Question 6 - Simple approximation décimale}
\subsubsection{Calcul de l'erreur}

	Pour $e$ = 2.7182818284, l'erreur de l'approximation est  :
	\begin{align*}
		\frac{27}{10} &= 2.7, erreur < 0.1 \\
		\frac{271}{100} &= 2.71, erreur < 0.01 \\
		\frac{2718}{1000} &= 2.718, erreur < 0.001 \\
		\frac{27182}{10000} &= 2.7182, erreur < 0.0001
	\end{align*}
	Pour une approximation décimale d'ordre $n$ l'erreur est donc $< 10^{-n}$.

\subsubsection{Application}
	Pour une approximation décimale à l'ordre n, $ x \simeq \frac{a_n}{10^n} $.
	L'ordre de grandeur de l'erreur est de $\frac{1}{10^{n}}$.
	Avec un développement en fraction continue, l'ordre de grandeur serait : $\frac{1}{b_n^2}$, soit $\frac{1}{(10^n)^2}$, donc beaucoup plus petit.
	
\section{Calcul de l'aire avec des fractions continues}
	
	%Q7
\subsection{Question 7 - Réduite d'ordre 3 de $\pi$ }
	Pour calculer la réduite d'ordre 3 de $\pi$ avec une résuite, il est nécessaire de connaître les quotients incomplets $q_1$, $q_2$ et $q_3$.
	
	Pour cela, calculons la fraction continue d'ordre 3.
	
	\begin{align*}
		\pi & \simeq 3 + 0.141592654 \\
		\pi & \simeq 3 + \frac{1}{\frac{1}{0.141592654}} \\
		\pi & \simeq 3 + \frac{1}{7 + \frac{1}{\frac{1}{0.062513285}}} \\
		\pi & \simeq 3 + \frac{1}{7 + \frac{1}{15 + \frac{1}{e}}} \\		
	\end{align*}
	
	On obtient :
	\[
		\left\{
			\begin{array}{rcr}
				q_1 &= 3 \\
				q_2 &= 7 \\
				q_3 &= 15 \\
			\end{array}
		\right.
	\]
	
	Sachant que  : 
	\[
		\left\{
			\begin{array}{rcr}
				a_0 &= 1 \\
				a_1 &= \lfloor \pi\rfloor = 3\\
				b_0 &= 0 \\
				b_1 &= 1 \\
			\end{array}
		\right.
	\]
	
	On applique ensuite les formules : 
	\[
		\left\{
			\begin{array}{rcr}
				a_n &= {q_n} \cdot a_{n-1} + a_{n-2} \\
				b_n &= {q_n} \cdot b_{n-1} + b_{n-2} \\
			\end{array}
		\right.
	\]
	
	pour calculer :
	\[
		\left\{
			\begin{array}{rcr}
				a_2 &= 22 \\
				b_2 &= 7
			\end{array}
		\right.
	\]
	
	\[
		\left\{
			\begin{array}{rcr}
				a_3 &= 333 \\
				b_3 &= 106
			\end{array}
		\right.
	\]
	
	La réduite d'ordre 3 de $\pi$ est : 
	\[
		\pi \simeq \frac{333}{106}
	\]
	
	%Q8
\subsection{Question 8 - Calcul de A(r) avec les réduites}
	Pour calculer l'aire du cercle, une possibilité est de remplacer $\pi$ par sa réduite d'ordre 3, soit :
	\[
		A(r) = \frac{333}{106} \cdot r \cdot r
	\]
	
	%Q9
\subsection{Question 9 - Erreur d'approximation}
	\begin{align*}
		A_3(r) &= \frac{333}{106} \cdot 534 \cdot 534 \\
		&= 895 820,26\ldots \\
		\Delta_3 &= A_0 - A_3 \approx 23
	\end{align*}
	
	L'erreur n'est pas beaucoup plus petite que celle obtenue avec une approximation décimale d'ordre 4 ($A_2$), mais c'est la meilleure.
	
	Nous remarquons cependant, que le résultat dépend de la définition de la réduite. Par exemple, pour l'université de Bordeaux : \url {http://www.labri.fr/perso/betrema/deug/poly/annexes/fc.html} ou sur Wikipedia : \url{http://fr.wikipedia.org/wiki/Fraction_continue}, le développement de la fraction continue démarre avec $q_0$ au lieu de $q_1$. 
	De cette manière, la réduite d'ordre 3 de $\pi$ est : 
	\[
		\pi \simeq \frac{355}{113}
	\]
	et bien sûr la précision obtenue est meilleure.
	\begin{align*}
		A_4(r) &= \frac{355}{113} \cdot 534 \cdot 534 \\
		&= 895 844,07\ldots \\
		\Delta_4 &= | A_0 - A_4 | \approx 0.08
	\end{align*}
